//左旋
TreeNode *RotateLeft(TreeNode *node);
{
    treeNode *tp=node->right;
   node->right=tp->left;
    tp->left=node;
    return t;
}

//右旋
 TreeNode *RotateRight(TreeNode *node);
 {
    treenode *t=node->left;
    node->left=t->right;
    t->right=node;
    return t;
 }

//左右旋
 TreeNode *RotateLeftRight(TreeNode*node);
 {
    treenode *t=node->left;
    node->left= rotateleft(t);
    return rotateright(node);

 }


//右左旋
 TreeNode *RotateRightLeft(TreeNode*node);
 {
    node->right=rotateright(node->right);
    return rotateleft(node);
 }
 //前中后层
 void show()
 {
    //前中后
    //层
    LinkQueen q;
    q.push(root);
    while(q.isEmpty!=nullptr)
    {
        treenode*node=*q.getfront();
        q.pop();
        std::cout<<node->data;
        if(node->left)
            q.push(node->left);
        if(node->right)
            q,push(node->right);
    }
    
 }
 //二叉树最大高度
 int GetTreeheight
 {
    return getnodeheight(root);


 }
 int getnodeheight(treenode*node)
 {
    if(node==nullptr)
        return;
    int leftheight=getnodeheight(node->left);
    int rightheight=getnodeheight(node->right);
    return (leftheight>rightheight?leftheigt+1:rightheight)+1;
 }

//左右高度差
int LRdevetion(treenode*node)
{
    if(node==nullptr)
        return 0;
    return getnodeheight(node->left)-getnoderight(node->right)
    
}
//二叉树插入

treenode * Insert(treenode *node,const elementtype& element)
{
    if(node==nullptr)
         return   treenode *newnode=new treenode(element)
    if(node->data==element)
        return node
    else if(node->data>element)
     {
         node->left=insert(node->left,element)
         if(LRdevetion>1)
         {
            if(node->left->data>element)
                RotateRight(node)
            else
                RotateLeftRight(node)
         }
     }
     else if(node->right<element)
     {
            node->right=insert(node->right,element);
            if(LRdevetion<-1)
        {
            if(node->right->data<element)
                RotateLeft(node)
            else
                RotateRightLeft(node);
                
        }
     }
     return node;

}
//二叉树查找
ElementType* FindByelement(treenode *node,element)
{
    return findnode(root,element)
}
ElementType* findnode(treenode *node,element)
{
    if(node==nullptr)
        return nullptr
    if(node->data=element)
        return &node->data
    if(node->data>element)
        return findenode(node->left,element)
    if(node->data<element)
        return findenode(node->right,element)
    return nullptr;
}
//二叉树删除
treenode* remove(treenode *node,element)
{
    root=removenode(root,element);
}
treenode *removenode(treenode *node,element)
{
    if(node==nullptr)
        return nullptr;
    if(node->data>element)
        return removenode(node->left);
    else if(node->data<element)
        return removenode(node->right);
    else
    {
        if(node->left==nullptr&&node->right==nullptr)
        {
            delete node; 
            return nullptr;
        }
        else  if(node->left!=nullptr&&node->right!=nullptr)
        {
            treenode *newnode=getminnode(node->right);
            node->data=newnode->data;
            node->right=removenode(node->right,newnode->data);
        }
        else
        {
           treenode *childnode=node->left?node->left:node->right;
           delete node;
           node= childnode;
        }
    }
    if(LRdevition(node)>1)
    {
        if(LRdevition(node->left)>0)
            RotateRight(node);
        
    }
    return node;
}


